package DEEPERsource.DEEPERsource.source.jung.entities;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

import org.apache.commons.collections.CollectionUtils;
import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

import edu.uci.ics.jung.graph.DirectedEdge;
import edu.uci.ics.jung.graph.DirectedGraph;
import edu.uci.ics.jung.graph.Edge;
import edu.uci.ics.jung.graph.Vertex;
import edu.uci.ics.jung.graph.impl.DirectedSparseEdge;
import edu.uci.ics.jung.graph.impl.SimpleUndirectedSparseVertex;
import edu.uci.ics.jung.graph.impl.SparseGraph;
import edu.uci.ics.jung.graph.impl.UndirectedSparseEdge;
import edu.uci.ics.jung.utils.UserData;
import exceptions.GraphException;
import graph.Keys;

/**
 * Special kind of graph for storing dependency trees. It is a directed graph
 * with possible parralel arcs.
 * 
 * @author tfayruzo
 * 
 */
public class Graph extends SparseGraph implements DirectedGraph, Keys {
	private static Log _log = LogFactory.getLog(Graph.class);

	//optional root for parse trees
	private Vertex root = null;

	// TODO: make it weak referenced
	private UndirectedGraph counterpart;

	/**
	 * Creates an instance of a sparse directed graph.
	 */
	public Graph() {
		super();
		Collection edge_predicates = getEdgeConstraints();
		edge_predicates.add(DIRECTED_EDGE);
	}
	
	public Graph(Vertex root){
		super();
		Collection edge_predicates = getEdgeConstraints();
		edge_predicates.add(DIRECTED_EDGE);
		this.root = root;
		addVertex(root);
	}

	// ------------------------NON INTERFACE PUBLIC METHODS----------------------
	public Vertex findVertex(Vertex v) {
		for (Object vert : mVertices) {
			Vertex _vert = (Vertex) vert;
			if (_vert.getUserDatum(INDEX).equals(v.getUserDatum(INDEX))) {
				return _vert;
			}
		}
		return null;
	}

	public Vertex findVertex(int index) {
		for (Object vert : mVertices) {
			Vertex _vert = (Vertex) vert;
			if (_vert.getUserDatum(INDEX).toString().equals(Integer.toString(index))) {
				return _vert;
			}
		}
		return null;
	}

	public DirectedEdge findEdge(int i) {
		for (Object edge : mEdges) {
			DirectedEdge _edge = (DirectedEdge) edge;
			if (_edge.getUserDatum(INDEX).equals(i)) {
				return _edge;
			}
		}
		return null;
	}
	
	public DirectedEdge findEdge(Vertex v1, Vertex v2) {
		for (Object edge : v1.getIncidentEdges()) {
			DirectedEdge _edge = (DirectedEdge) edge;
			if (_edge.getOpposite(v1).equals(v2)) {
				return _edge;
			}
		}
		return null;
	}
	
	public NewPath getNewPath(Vertex v1, Vertex v2) throws GraphException{
		if (v1 == null || v2 == null) {
			throw new NullPointerException("One of the vertices is null");
		}
		
		// both vertices sould belong to dep tree
		if (v1.getGraph() != this || v2.getGraph() != this) {
			_log.info("Given vertices does not belong to the graph. Trying to search them in the graph");
			boolean fail = false;
			if(v1.getUserDatum(INDEX)!=null && v2.getUserDatum(INDEX)!=null){
				v1 = findVertex((Integer)v1.getUserDatum(INDEX));
				v2 = findVertex((Integer)v2.getUserDatum(INDEX));
				if(v1==null || v2==null)
					fail = true;
			}else{
				fail = true;
			}
			if(fail){
				_log.error("Path constructor: Vertices should belong to graph");
				return null;
			}				
		}
		
		if (counterpart == null) {
			counterpart = transform();
		}		
		List<Edge> edges = counterpart.getPath(v1, v2);		
		NewPath path = new NewPath(edges.size()+1);
		List<Vertex> vertices = new ArrayList<Vertex>();
		int i = 0;
		boolean first = true, last = false;
		Vertex tmp = null;
		for(Iterator<Edge> it = edges.iterator(); it.hasNext();){
			DirectedEdge edge = findEdge((Integer)it.next().getUserDatum(INDEX));
			if(!it.hasNext()){
				last = true;
			}
			path.edges[i] = edge;
			if(first){				
				vertices.add(v1);
				tmp = edge.getOpposite(v1);
				vertices.add(tmp);
				path.eMarks[i] = getDirection((Integer)v1.getUserDatum(INDEX), (Integer)tmp.getUserDatum(INDEX));
				/*if(v1.isDest(edge))
					path.eMarks[i] = "in";
				else
					path.eMarks[i] = "out";
					*/				
				first = false;
			}else if(last){
				vertices.add(v2);
				path.eMarks[i] = getDirection((Integer)tmp.getUserDatum(INDEX), (Integer)v2.getUserDatum(INDEX));
				/*if(tmp.isDest(edge))
					path.eMarks[i] = "in";
				else
					path.eMarks[i] = "out";
					*/
			}else{
				Vertex tmp2 = tmp;
				tmp = edge.getOpposite(tmp);				
				path.eMarks[i] = getDirection((Integer)tmp2.getUserDatum(INDEX), (Integer)tmp.getUserDatum(INDEX));
				/*if(tmp.isSource(edge))
					path.eMarks[i] = "in";
				else
					path.eMarks[i] = "out";
				*/
				vertices.add(tmp);
			}
			i++;
		}
		
		i = 0;
		for(Vertex v : vertices){
			path.vertices[i] = v;
			if(v.equals(v1)){
				if(path.eMarks[i].equals("in"))
					path.vMarks[i] = "bottom";
				else
					path.vMarks[i] = "top";
			}else if(v.equals(v2)){
				if(path.eMarks[i-1].equals("in"))
					path.vMarks[i] = "top";
				else
					path.vMarks[i] = "bottom";
			}else{
				if(path.eMarks[i-1].equals(path.eMarks[i])){
					path.vMarks[i] = "inner";
				}else if(path.eMarks[i-1].equals("in")){
					path.vMarks[i] = "top";
				}else{
					path.vMarks[i] = "bottom";
				}
			}
			i++;
		}	
		return path;
	}

	// -------------------------PRIVATE METHODS-------------------------------
	/*
	 * Specific graph trasformation, transforms directed graph to undirected
	 * counterpart. As far as I understood could not be performed by copy() or
	 * whatever methods in JUNG. @return
	 */
	private UndirectedGraph transform() {
		UndirectedGraph graph = new UndirectedGraph();
		for (Object v : mVertices) {
			Vertex _vert = (Vertex) v;
			Vertex newV = new SimpleUndirectedSparseVertex();
			newV.setUserDatum(INDEX, _vert.getUserDatum(INDEX),
							UserData.SHARED);
			newV.setUserDatum(LABEL, _vert.getUserDatum(LABEL),
							UserData.SHARED);
			if(_vert.getUserDatum(POS)!=null){
				newV.setUserDatum(POS, _vert.getUserDatum(POS),
						UserData.SHARED);
			}
			graph.addVertex(newV);
		}
		for (Object e : mEdges) {
			Edge _e = (Edge) e;
			Vertex v1 = (Vertex) _e.getEndpoints().getFirst();
			Vertex v2 = (Vertex) _e.getEndpoints().getSecond();
			Edge newE = new UndirectedSparseEdge(graph.findVertex(v1), graph
					.findVertex(v2));
			newE.setUserDatum(INDEX, _e.getUserDatum(INDEX), UserData.SHARED);
			if(_e.getUserDatum(LABEL)!=null){
				newE.setUserDatum(LABEL, _e.getUserDatum(LABEL), UserData.SHARED);
			}			
			graph.addEdge(newE);
		}
		return graph;
	}
	
	// returns "out" if v1 dominates v2, "in" - otherwise  
	private String getDirection(int vInd1, int vInd2){
		Vertex v1 = findVertex(vInd1);
		Vertex v2 = findVertex(vInd2);
		DirectedEdge e = findEdge(v1, v2);
		if(e.getSource().equals(v1))
			return "out";
		else
			return "in";
	}

	public String serialize() {
		StringBuffer sb = new StringBuffer();
		if(root!=null){
			sb.append("\nROOT\n");
			sb.append(root.getUserDatum(INDEX));
			sb.append("\t");
			if(root.getUserDatum(LABEL)==null)
				sb.append(root.getUserDatum("null"));
			else
				sb.append(root.getUserDatum(LABEL));
			sb.append("\t");
			if(root.getUserDatum(POS)==null)
				sb.append(root.getUserDatum("null"));
			else
				sb.append(root.getUserDatum(POS));
			sb.append("\n");
		}
		sb.append("\nVERTICES\n");
		for (Object o : mVertices) {
			Vertex v = (Vertex) o;
			sb.append(v.getUserDatum(INDEX));
			sb.append("\t");
			if(v.getUserDatum(LABEL)==null)
				sb.append(v.getUserDatum("null"));
			else
				sb.append(v.getUserDatum(LABEL));
			sb.append("\t");
			if(v.getUserDatum(POS)==null)
				sb.append(v.getUserDatum("null"));
			else
				sb.append(v.getUserDatum(POS));			
			sb.append("\n");
		}
		sb.append("\nEDGES\n");
		for (Object o : mEdges) {
			DirectedEdge e = (DirectedEdge) o;
			sb.append(e.getSource().getUserDatum(INDEX));
			sb.append("\t");
			sb.append(e.getDest().getUserDatum(INDEX));
			sb.append("\t");
			sb.append(e.getUserDatum(INDEX));
			sb.append("\t");
			if(e.getUserDatum(LABEL)==null)
				sb.append(e.getUserDatum("null"));
			else
				sb.append(e.getUserDatum(LABEL));
			sb.append("\n");
		}
		sb.append("\n");
		return sb.toString();
	}

	public static Graph deserialize(BufferedReader stream) throws IOException {
		Graph g = null;
		String s;
		boolean vertices = false;
		boolean edges = false;
		boolean root = false;
		while ((s = stream.readLine()) != null) {
			if(s.equals("")){
				continue;
			}
			if (s.equals("EDGES")) {
				edges = true;
				vertices = false;
				root = false;
				continue;
			}else if(s.equals("VERTICES")){
				if(g == null)
					g = new Graph();
				edges = false;
				vertices = true;
				root = false;
				continue;
			}else if(s.equals("ROOT")){
				edges = false;
				vertices = false;
				root = true;
				continue;
			}
			String[] split = s.split("\t");
			if (vertices) {
				Vertex v = new DependencyVertex();
				v.setUserDatum(INDEX, split[0], UserData.SHARED);
				if(!split[1].equals("null"))
					v.setUserDatum(LABEL, split[1], UserData.SHARED);
				if(!split[2].equals("null"))
					v.setUserDatum(POS, split[2], UserData.SHARED);
				g.addVertex(v);
			} else if(edges){
				Vertex v1 = g.findVertex(Integer.parseInt(split[0]));
				Vertex v2 = g.findVertex(Integer.parseInt(split[1]));
				DirectedEdge e = new DirectedSparseEdge(v1, v2);
				e.setUserDatum(INDEX, split[2], UserData.SHARED);
				if(!split[3].equals("null"))
					e.setUserDatum(LABEL, split[3], UserData.SHARED);
				g.addEdge(e);
			}else if(root){
				Vertex r = new DependencyVertex();
				r.setUserDatum(INDEX, split[0], UserData.SHARED);
				if(!split[1].equals("null"))
					r.setUserDatum(LABEL, split[1], UserData.SHARED);
				if(!split[2].equals("null"))
					r.setUserDatum(POS, split[2], UserData.SHARED);
				g = new Graph(r);
			}
		}
		return g;
	}
}